/*
*	贪心算法
*/



//柠檬水找零
//https://leetcode.cn/problems/lemonade-change/submissions/
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int Five = 0;   //五块钱
        int Ten = 0;    //十块钱
        for(const int& m:bills) //优先用10 再考虑用5
        {
            if(m == 5) ++Five;
            else if(m == 10)
            {
                if(Five) --Five;
                else return false;
                ++Ten;
            }
            else
            {
                if(Ten && Five) //找10+5
                {
                    --Ten;
                    --Five;
                }
                else if(Five >= 3) Five -= 3; //找三个5块
                else return false;
            }
        }
        return true;
    }
};



//将数组和减半的最少操作次数
//https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/submissions/
class Solution {
public:
    int halveArray(vector<int>& nums) {
        double sum = 0;
        priority_queue<double> pq;
        for (const int n : nums)
        {
            sum += n;
            pq.push(n);
        }
        sum /= 2.0;

        int ret = 0;
        while (sum > 0)
        {
            ++ret;
            double num = pq.top()/2.0; pq.pop();
            sum -= num;
            pq.push(num);
        }

        return ret;
    }
};



//最大数
//https://leetcode.cn/problems/largest-number/submissions/
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        //两个字符串组合
        // s1+s2 和 s2+s1 取最大值 因为字符0-9有序 所以直接比较字符串即可
        vector<string> vs;
        int sz = 0;
        for(int& n:nums) 
        {
            vs.push_back(to_string(n));
            sz += vs.back().size();
        }
        sort(vs.begin(),vs.end(),[](const string& s1,const string& s2){
            return (s1+s2) > (s2+s1);
        });
        //例如 11 22 要么组成 1122 要么 2211 显然 2211 比较大 在字符中 '2' > '1'

        if(vs[0][0] == '0') return "0";
        string ret;
        ret.reserve(sz+10);
        for(string& s:vs) ret += s;
        return ret;
    }
};



//摆动序列
//https://leetcode.cn/problems/wiggle-subsequence/submissions/
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return n;

        int ret = 0,right = 0,left = 0;
        for(int i = 0;i<n-1;++i)
        {
            right = nums[i+1]-nums[i]; //查看趋势 如果 >0 则是上升趋势 <0 则是下降趋势
            if(right == 0) continue; //如果相等则遍历下一个
            if(left*right <= 0) ++ret; //如果下降 则表示一个波动趋势
            left = right; //一直上升left和right都为正 一直下降 left和right都为负 最终相乘都为正 只有出现波峰波谷才会呈现负数
        }
        return ret+1; //最后一个数没有算入 应该算入
    }
};



//最长递增子序列-贪心(动态规划+二分优化)
//https://leetcode.cn/problems/longest-increasing-subsequence/description/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> v; //里面存比当前位置小的值 如果大于则push_back
        v.push_back(nums[0]);
        for(int i = 1;i<n;++i)
        {
            if(nums[i] > v.back()) v.push_back(nums[i]);
            else if(nums[i] < v.back())
            {
                int left = 0,right = v.size();
                while(left < right) //找交换位
                {
                    int mid = (left+right)/2;
                    if(nums[i] > v[mid]) left = mid+1;
                    else right = mid;
                }
                v[left] = nums[i];
            }
        }
        return v.size();
    }
};



//递增的三元子序列
//https://leetcode.cn/problems/increasing-triplet-subsequence/submissions/
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n<3) return false;
        
        //与最长子序列思想相似
        int tmp[2] = {nums[0],INT_MAX};
        for(int i = 1;i<n;++i)
        {
            if(nums[i] > tmp[1]) return true; //如果该数比第二个数还大 则存在第三个数 组成子序列
            else if(nums[i] > tmp[0]) tmp[1] = nums[i]; //该数大一第一个数 则更新第二个数
            else tmp[0] = nums[i]; //否则更新第三个数
        }
        return false;
    }
};




//674.最长连续递增序列
//https://leetcode.cn/problems/longest-continuous-increasing-subsequence/submissions/
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return n;
        int ret = 0;
        int left = 0,right = 0;
        while(right < n-1)
        {
            if(nums[right] >= nums[right+1])
            {
                ret = max(ret,right-left+1);
                left = right = right+1;
            }
            else ++right;
        }
        ret = max(ret,right-left+1);
        return ret;
    }
};



//买卖股票的最佳时机
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/submissions/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        int minprev = prices[0]; //前i-1个数中的最小值
        int n = prices.size();

        for(int i = 0;i<n;++i)
        {
            ret = max(ret,prices[i]-minprev);
            minprev = min(prices[i],minprev);
        }
            
        return ret;
    }
};



//买卖股票的最佳时机II
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/submissions/
class Solution {
public:
    // int maxProfit(vector<int>& prices) { //拆分 算每一笔的收益
    //     int n = prices.size();
    //     int ret = 0;
    //     for(int i = 1;i<n;++i) //只要股票每天都在涨 就累加收益 一旦下降就不买
    //     {
    //         if(prices[i] > prices[i-1]) 
    //             ret +=  prices[i]-prices[i-1];
    //     }
    //     return ret;
    // }

    int maxProfit(vector<int>& prices) { //算上升期的收益
        int n = prices.size();
        int ret = 0;
        int i = 0;
        while(i<n)
        {
            int j = i;
            while(j+1<n && prices[j]<prices[j+1]) ++j; //找股票下降点 下降点到下一个下降点就是一个最高收益
            ret += prices[j]-prices[i];
            i = j;
            ++i;
        }
        return ret;
    }
};



//K次取反后最大化的数组和
//https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/submissions/
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int n = nums.size();
        int negnum = 0; //负数个数
        int minum = INT_MAX; //所有数中绝对值数最小的
        for(const int num:nums)
        {
            negnum += num<0;
            minum = min(minum,abs(num));
        }
        // negnum >= k 将前k个最小的负数变成正数
        // negnum < k 将所有负数变成正数 对绝对值最小的数操作 如果k-negnum为奇数则取负 否则取正

        int ret = 0;
        if(negnum >= k)
        {
            sort(nums.begin(),nums.end());
            int pos = 0;
            while(pos < k) ret += -nums[pos++];
            while(pos < n) ret += nums[pos++];
        }
        else
        {
            for(const int num:nums) ret += abs(num);
            if((k-negnum)%2) ret -= minum*2; //此时该数肯定为正数 我们此前加上了一次 这里取负要减去2次
        }
        return ret;
    }
};



//按身高排序
//https://leetcode.cn/problems/sort-the-people/submissions/
class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        //对下标排序
        vector<int> pos(n);
        for(int i = 0;i<n;++i) pos[i]=i;

        sort(pos.begin(),pos.end(),[&](int x,int y){
            return heights[x] > heights[y];
        });

        vector<string> ret;
        ret.reserve(n);
        for(int i = 0;i<n;++i) ret.push_back(names[pos[i]]);

        return ret;
    }
};



//优势洗牌
//https://leetcode.cn/problems/advantage-shuffle/
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> pos(n);
        for(int i = 0;i<n;++i) pos[i]=i;

        //将两个数组排序 
        //如果nums1的数比不过当前nums2的数 就去匹配nums2中最大的数
        sort(nums1.begin(),nums1.end());
        sort(pos.begin(),pos.end(),[&](int x,int y) {
            return nums2[x] < nums2[y];
        });

        vector<int> ret(n);
        int left = 0,right = n-1;
        for(int x:nums1)
        {
            //取nums2中排序后的第一个数(最小的数)
            if(nums2[pos[left]] < x) ret[pos[left++]] = x; //如果能比过就放在这里
            else  ret[pos[right--]] = x; //不能就去匹配最大的数 废物利用最大化
            //但是匹配的下标必须是排序前的下标 返回的也是排序前的
            //所以pos[0]存储的就是排序前nums2中的第一个数的下标
        }
        return ret;
    }
};



// 最长回文串
// https://leetcode.cn/problems/longest-palindrome/submissions/
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> hash;
        for(char c:s) ++hash[c];

        int count = 0;
        int ret = 0;
        for(auto& [k,v]:hash)
            //我们要求奇数-1再加上 偶数则直接加上
            ret += (v/2)*2;
        
        if(ret < s.size()) ret += 1;
        return ret;
    }
};




//增减字符串匹配
//https://leetcode.cn/problems/di-string-match/submissions/
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int left = 0,right = s.size();
        vector<int> ret;
        ret.reserve(right);
        for(char c:s)
        {
            if(c == 'I') ret.push_back(left++);
            else ret.push_back(right--);
        }
        ret.push_back(right);
        return ret;
    }
};



//分发饼干
//https://leetcode.cn/problems/assign-cookies/submissions/
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int gn = g.size(), sn = s.size();
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int ret = 0;
        for(int i=0,k=0;i<gn&&k<sn;++i,++k)
        {
            while(k<sn&&g[i]>s[k]) ++k; //找到可以满足第i个孩子胃口的饼干
            if(k < sn) ++ret; //如果在末尾表示没有饼干可以满足 否则满足一个小孩子
        }
        return ret;
    }
};



//最优除法-利用分子分母的大小控制除数大小
//https://leetcode.cn/problems/optimal-division/submissions/
class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return to_string(nums[0]);
        if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);

        string ret;
        ret.reserve(n*3);

        ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for(int i = 2;i<n;++i)
            ret += "/" + to_string(nums[i]);
        ret += ')';

        return ret;
    }
};



//跳跃游戏II
//https://leetcode.cn/problems/jump-game-ii/description/
class Solution {
public:
    int jump(vector<int>& nums) {
        int left = 0,right = 0,ret = 0,maxpos = 0,n = nums.size();

        //层序遍历思想 一层一层跳
        while(left <= right)
        {
            if(maxpos >= n-1) return ret;
            //在当前层中选择最大的跳跃距离数跳最远
            for(int i = left;i<=right;++i)
                maxpos = max(maxpos,nums[i]+i);

            //更新区间 前往下一层
            left = right+1;
            right = maxpos;
            ++ret;
        }
        return ret;
    }
};



//跳跃游戏
//https://leetcode.cn/problems/jump-game/submissions/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int left = 0,right = 0,maxpos = 0,n = nums.size();

        //层序遍历思想 一层一层跳
        while(left <= right)
        {
            if(maxpos >= n-1) return true; //可以到达n-1
            for(int i = left;i<=right;++i)
                maxpos = max(maxpos,nums[i]+i);

            //更新区间 前往下一层
            left = right+1;
            right = maxpos;
        }
        //跳出循环表示无法到达
        return false;
    }
};



//加油站
//https://leetcode.cn/problems/gas-station/submissions/
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();

        //把数组当成循环队列 每次选一个起点遍历一圈数组 能够保证遍历一圈剩余油量大于等于0则返回该起点下标
        for(int i = 0;i<n;++i) //每次选一个起点
        {
            int count = 0; //油量
            for(int k = 0;k<n;++k)
            {
                //当前加油站油量减去耗油量即可
                count += (gas[(i+k)%n]-cost[(i+k)%n]);
                if(count < 0)
                {
                    //如果count小于0 则前面无论怎么凑都无法凑出大于0的油量 前i个加油站可以不选择为起点 转而选择i+1
                    i += k; //优化
                    break;
                }
            }
            if(count >= 0) return i;
        }

        return -1;
    }
};



//单调递增的数字
//https://leetcode.cn/problems/monotone-increasing-digits/description/
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int sz = s.size();
        int i = 0;
        while(i+1 < sz && s[i] <= s[i+1]) ++i; //找单调递增的区间 直到单调递减
        if(i == sz-1) return n; //如果遍历完了整个数 则整个数就是单调递增

        while(i-1 >= 0 && s[i] == s[i-1]) --i; //看有多少相等的数 

        --s[i++]; //相等数减少1 后面的数全部为9
        while(i<sz) s[i++] = '9';
        return stoi(s);
    }
};



//坏了的计算器
//https://leetcode.cn/problems/broken-calculator/submissions/
class Solution {
public:
    int brokenCalc(int startValue, int target) {
        //正难则反
        //将target通过除和+1还原成startValue
        int ret = 0;
        while(target > startValue)
        {
            if(target%2 == 0) target /= 2;
            else ++target;
            ++ret;
        }
        //出来肯定是 target<=startValue 剩下的差距有用加法即可
        return ret + startValue - target;
    }
};



//合并区间
//https://leetcode.cn/problems/merge-intervals/submissions/
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();

        //默认按intervals[i][0] 排序
        sort(intervals.begin(),intervals.end());

        int left = intervals[0][0],right = intervals[0][1];
        vector<vector<int>> ret;
        for(int i = 1;i<n;++i)
        {
            //左区间在当前区间内 - 更新右区间
            if(intervals[i][0] <= right) right = max(right,intervals[i][1]);
            else
            {
                ret.push_back({left,right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        ret.push_back({left,right}); //最后一个区间
        return ret;
    }
};



//无重叠区间
//https://leetcode.cn/problems/non-overlapping-intervals/submissions/
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();

        //按左端点排序
        sort(intervals.begin(),intervals.end());
        int right = intervals[0][1];

        int ret = 0;
        for(int i = 1;i<n;++i)
        {
            //重叠区间 删除区间比较大的 留下小区间
            if(intervals[i][0] < right) //后面区间的左端点比当前区间的右端点小 发生重叠
            {
                ++ret;
                right = min(right,intervals[i][1]); //调整右区间
            }
            else right = intervals[i][1]; //调整右区间转而继续对比
        }
        return ret;
    }
};




//用最少数量的箭引爆气球
//https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/submissions/
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(),points.end());

        int right = points[0][1];
        int ret = 1; //默认一只箭
        for(int i = 1;i<n;++i)
        {
            //求交集 只要可以相交就可以一只箭引爆
            if(right >= points[i][0]) right = min(right,points[i][1]);
            else //不能相交 则先射箭引爆 再更换区间
            {
                right = points[i][1];
                ++ret;
            }
            
        } 
        return ret;
    }
};




//整数替换
//https://leetcode.cn/problems/integer-replacement/submissions/
class Solution {
public:
    int integerReplacement(int n) {
        int ret = 0;

        //我们仅考虑32位整数中的最后两位比特位 重要的是消除更多的 1
        //1001 时我们 -1 即可  >1
        //0111 时我们只需 +1 即可  >3
        //0011 时 我们只需要 +1即可  ==3
        while(n > 1)
        {
            if(n%2 == 0)
            {
                n /= 2;
                ++ret;
            }
            else
            {
                if(n == 3)
                {
                    ret += 2; // (n-1)/2
                    n = 1;
                }
                else if(n%4 == 1)
                {
                    n = (n-1)/2;
                    ret += 2;
                }
                else
                {
                    n = n/2+1; //(n+1/2会溢出 n/2+1与其结果相同)
                    ret += 2;
                }
            }
        }

        return ret;
    }
};



//俄罗斯套娃信封问题
//https://leetcode.cn/problems/russian-doll-envelopes/submissions/
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //我们直接排序 会出现左端点相同 右端点(宽)升序的情况
        //[2,1] [2,2] [2,3] ...
        //此时我们还需要额外分情况讨论
        //如果我们改变排序策略 左端点相同时 右端点按升序排序就可以避免 因为左端点相同时右端点大也没用了

        int n = envelopes.size();
        sort(envelopes.begin(),envelopes.end(),[&](const vector<int>& v1,const vector<int>& v2){
            return v1[0]==v2[0]?v1[1]>v2[1]:v1[0]<v2[0];
        });

        vector<int> ret;
        ret.reserve(n);
        ret.push_back(envelopes[0][1]);
        //因为排序了 我们只考虑右端点
        for(int i = 1;i<n;++i)
        {
            //比当前数组中最大的还大 则子序列变长
            if(envelopes[i][1] > ret.back()) ret.push_back(envelopes[i][1]);
            else //找一个最佳插入位置将值改为该值
            {
                int left = 0,right = ret.size()-1;
                while(left < right)
                {
                    int mid = (left+right)/2;
                    if(ret[mid] < envelopes[i][1]) left = mid+1;
                    else right = mid;
                }
                ret[left] = envelopes[i][1];
            }
        }
        return ret.size();
    }
};



//可被三整除的最大和
//https://leetcode.cn/problems/greatest-sum-divisible-by-three/submissions/
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // 我们选出 num%3==1 和 num%3==2 倒数第一和第二小的数
        const int INF = 0x3f3f3f3f;
        int x1=INF,x2=INF,y1=INF,y2=INF;
        int sum = 0;
        for(int n:nums)
        {
            sum += n;
            if(n%3 == 1)
            {
                if(x1 > n) x2 = x1,x1 = n;
                else if(x2 > n) x2 = n;
            }
            else if(n%3 == 2)
            {
                if(y1 > n) y2 = y1,y1 = n;
                else if(y2 > n) y2 = n;
            }
        }

        if(sum%3 == 0) return sum;
        else if(sum%3 == 1) return max(sum-x1,sum-y1-y2);
        return max(sum-x1-x2,sum-y1); //sum%3==2
    }
};



//距离相等的条形码
//https://leetcode.cn/problems/distant-barcodes/submissions/
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> hash;
        int maxVal = 0,maxCount = 0;

        //记录每一个数出现的次数 然后分隔摆放
        // 111 223  先摆放出现次数最多的
        // 1 1 1  摆放最多的1
        // 12121  //摆放2
        // 121213
        int n = barcodes.size();
        for(int x:barcodes)
        {
            if(maxCount < ++hash[x])
            {
                maxCount = hash[x];
                maxVal = x;
            }
        }

        int pos = 0;
        vector<int> ret(n);
        for(int i = 0;i<maxCount;++i)
        {
            ret[pos] = maxVal;
            pos += 2;
        }

        hash.erase(maxVal);
        //开始摆放剩下的数
        for(auto& [k,v]:hash)
        {
            for(int i = 0;i<v;++i)
            {
                if(pos >= n) pos = 1;
                ret[pos] = k;
                pos += 2;
            }
        }
        return ret;
    }
};



//重构字符串
//https://leetcode.cn/problems/reorganize-string/submissions/
class Solution {
public:
    string reorganizeString(string s) {
        int n = s.size();
        unordered_map<char,int> hash;
        int maxCount = 0;
        char maxVal = 0;
        for(char c:s)
        {
            if(maxCount < ++hash[c]) 
            {
                maxCount=hash[c];
                maxVal = c;
            } 
        }
        if(maxCount > (n+1)/2) return ""; //如果最多的字符超过一半 则必有相邻的

        string ret;
        ret.resize(n);
        int pos = 0;
        for(int i = 0;i<maxCount;++i)
        {
            ret[pos] = maxVal;
            pos += 2;
        }
        hash.erase(maxVal);
        for(auto& [k,v]:hash)
        {
            for(int i = 0;i<v;++i)
            {
                if(pos >= n) pos = 1;
                ret[pos] = k;
                pos += 2;
            }
        }

        return ret;
    }
};



